1. Field of the Invention
The present invention relates to a decoder utilized in the receiving end of a data communication system for correcting bit errors in a received digital data. In particular, the received digital data have been encoded into BCH (Bose-Chaudhuri-Hocquenghem) codes before being transmitted.
2. Description of Prior Art
In a digital data communication system which sends out digital information through a channel to a receiver, due to noises and/or distortions, the received digital informations often contain a number of bit errors. To overcome this problem, a BCH encoding and decoding technique is often utilized. The BCH encoding and decoding technique has been developed respectively and independently by Bose, Chaudhuri, and Hocquenghem.
Referring to FIG. 1, there is shown the schematic diagram of a digital communication system. In the digital communication system, the transmitter thereof includes a BCH encoder 1 and a modulator 2 and the receiver thereof includes a demodulator 4 and a BCH decoder 5. A message information which is to be transmitted is firstly converted to a series of binary words, each of which has a bit length of k as shown in FIG. 2. A binary word in the message information is often represented by a polynomial I(x), where EQU I(x)=I.sub.0 +I.sub.1 .multidot.x+I.sub.2 .multidot.x.sup.2 + . . . +I.sub.k-1 .multidot.x.sup.k-1
where I.sub.p, p=0,1,2, . . . k-1 are the bits constituting the binary word and I.sub.0 is the lowest order bit and I.sub.k-1 is the highest order bit. Each of the binary words I(x) is then processed by the BCH encoder 1 in such a way that a number of check bits are appended to the lowest order bits I.sub.0 to form a codeword with a bit length of n and which is represented by a polynomial C(x), where EQU C(x)=c.sub.0 +c.sub.1 .multidot.x+c.sub.2 .multidot.x.sup.2 + . . . +c.sub.n-1 .multidot.x.sup.n-1
wherein C.sub.0 to C.sub.n-k-1 are the check bits and C.sub.n-k to C.sub.n-1 are the information bits.
The codewords are then modulated by the modulator 2 for transmission and then transmitted via a channel 3 to the receiver of the communication system. The demodulator 4 demodulates the received signal into a series of binary words, each of which corresponds to a codeword. If there is not bit errors occurred in a received word, the bit pattern thereof is the same as the corresponding codeword. Otherwise, the bit pattern of the received word is different from that of the corresponding codeword and the difference therebetween is called an error pattern of the received word. The error pattern can be expressed by a polynomial as: EQU E(x)=e.sub.0 +e.sub.1 .multidot.x+e.sub.2 .multidot.x.sup.2 + . . . +e.sub.n-1 .multidot.x.sup.n-1
Accordingly, the received word R(x) can be expressed as: ##EQU1## The BCH decoder 5 is employed for detecting if there is any bit error occurred in each of the received words and performing necessary correcting actions to the erroneous bits.
If the BCH decoding technique utilized herein allows the BCH decoder 5 to detect and correct at most t erroneous bit in each received word, the codeword is denoted as a t-error-correcting (n, k, d.sub.min) bp BCH code, where
n is the block length of the codeword and n=2.sup.m -1, m is an integer and m.gtoreq.3; PA1 k is the number of the information bits in the codeword and k.gtoreq.n-mt; and PA1 d.sub.min is the minimum distance of code and d.sub.min .gtoreq.2t+1. PA1 (a) calculating the syndrome values S.sub.i, i=1,2, . . . ,2t, where t is the maximum number of bit errors guaranteed to be corrected, from the polynomial R(x) of a received codeword; PA1 (b) determining an error-location polynomial .sigma.(x) from the syndrome values S.sub.i, i=1,2, . . . ,2t; PA1 (c) determining the locator(s) of the erroneous bit(s) by finding the roots of .sigma.(x)=0.
For a thorough and more detailed understanding of the BCH codes, readers may turn to a textbook "Error Control Coding: Fundamental and Applications" authored by Shu Lin & Daniel J. Costello, Jr. and published by Prentice Hall.
The bit errors occurred in a received binary word that has been encoded into a t-error-correcting BCH codeword can all be corrected faithfully if the total number of the bit errors is equal to or less than t, where t is a predetermined number. A selection of a larger t will lead to a longer length of the check bits in a codeword and to a more complex decoding process.
Among the methods of decoding binary BCH codes, a standard algebraic decoding method is most commonly used. The standard algebraic decoding method comprises essentially the following three steps of:
For the Step (b), an iteration algorithm proposed by Berlekamp is best known. And for the Step (c), a search algorithm proposed by Chien is considered to be the most efficient method. Generally speaking, the development of an algorithm for performing the task of Step (b) is most complicated and tedious.
Another algebraic decoding method, known as a step-by-step decoding method, has been proposed by Massey in 1965 for the decoding of BCH codes. The method proposed by Massey comprises the following steps of:
STEP (0): PA0 STEP (1): PA0 STEP (2): PA0 STEP (3): PA0 STEP (4): PA0 STEP (5):
Set j=0.
Determine from s(X) whether det(L.sub.t)=0.
If det(L.sub.t)=0, complement s.sub.i, increase j by one, and go to STEP (1). Otherwise, set j=1 and go to STEP (3).
Temporarily complement r.sub.n-j and determine from the modified syndrome whether det(L.sub.t)=0.
If det(L.sub.t)=0, set r.sub.n-j =r.sub.n-j +1. Otherwise, set r.sub.n-j=r.sub.n-j.
If j=n-r, stop. Otherwise, increase j by one and go to STEP (3).
For the definitions of the denotations used and a detailed understanding of the foregoing algorithm and the overall step-by-step decoding method according to Massey, readers are directed to a technical paper entitled "Step-by-step Decoding of the Bose-Chaudhuri-Hocquenghem Codes" published on IEEE TRANSACTIONS ON INFORMATION THEORY, Vol. IT-11, No. 4, pp. 580-585, Oct., 1965.
The basic principle of the step-by-step decoding method according to Massey is that each of the bits constituting a received binary word is inverted one at a time to form a new word, and then the new word is tested to see if the weight of the error pattern (the number of erroneous bits) thereof is reduced or increased. If reduced, the bit that has been inverted is an erroneous bit; otherwise if increased, the bit is a correct bit.
The step-by-step decoding method proposed by Massey does not include steps of calculating the coefficients of the error location polynomial .sigma.(x) and searching for the roots of the same. As a result, the step-by-step decoding method is less complex than the standard algebraic method.
Despite the advantage, the step-by-step decoding method according to Massey is, however, still not considered appropriate to be implemented by hardware, i.e. by logic circuits. By Massey's method, the bit errors in the received word R(x) is achieved by determining whether the value det(L.sub.t) is zero or not (see STEP(2)). As a consequence, even if the total number of erroneous bits in a received word is much less than t, a special circuit must be used to change the values of some of the correct bits in the received word until the weight of the error pattern has reached t.
In addition, the Massey's method use the element .alpha..sup.n-1 to complement the syndrome values (see STEP (3) and FIG. 1 in Massey's technical paper). As a consequence, all the m bits constituting each syndrome values might need to be inverted one by one.